The present invention relates generally to the display of data by output devices, and more particularly to a method and apparatus for interpolating a higher resolution image from a lower resolution image to create a higher displayed visual quality of the image.
A computer system can output data to a wide variety of output display devices. Output display devices such as laser printers, plotters, and other printing devices produce an image on a sheet of paper or other physical surface or media, while output display devices such as computer monitors and flat-panel display devices develop visual representations on a computer screen.
Many output display devices receive display data in the form of a "bitmap" or "pixel map" and generate images from the display data. A pixel is a fundamental picture element of an image generated by an output display device, and a bitmap is a data structure including information concerning a number of pixels of the representation. Bitmaps that contain more than on/off information, such as color values, are often referred to as "pixel maps." As used herein, both bitmaps and pixel maps are referred to as "bitmaps." For example, a printer can print dots on a piece of paper corresponding to the information of a bitmap. Alternatively, a computer monitor can illuminate pixels based upon the information of the bitmap. The term "image" is used interchangeably with the term "bitmap" to refer to both the data that is provided to an output display device as well as the actual outputted visual representation displayed by the display device. A "raster" output device creates a visual representation by displaying the array of pixels arranged in rows and columns from the bitmap. Most output devices, other than plotters, are raster output devices.
Images are typically displayed with a number of different shades or colors assigned to each of the pixels of the image. Herein, the term "gray level" is used to refer to the particular shade, color, and/or brightness of a pixel. For example, an output display device that can display 256 "gray levels" might display 256 shades of gray, or, alternatively, 256 different colors or shades of colors. Many examples herein refer to gray levels between the extreme gray levels of black (or dark) at one end of the scale and white (or light) at the opposing end of the scale. The intermediate gray levels between these extremes are displayed as shades of gray or as different colors such as red, yellow, blue, etc., or shades of different colors. Images are also specified with a resolution. There are two types of resolution referred to herein: spatial resolution and "gray level" (or "tonal") resolution. Spatial resolution refers to the number of pixels per unit dimension in an image, and is often expressed as dots per inch (dpi) or pixels per inch. Gray level resolution refers to the amount of different gray levels that can be displayed in an image; the greater the number of gray levels that can be displayed, the greater the gray level resolution.
Images can be specified with a bitmap depth or pixel depth, i.e., as an "n-bit" bitmap or "n-bit" image, which signifies how many gray levels can (potentially) be displayed in the image. The number of gray levels displayed is equal to 2.sup.n ; for example, a 2-bit image allows the the output device to display 4 gray levels, a 4-bit image allows the output device to display 16 gray levels, etc. Some output display devices can display an individual pixel at one of multiple available gray levels. For example, a display device with pixel depth of 4 bits can display a pixel in one of 16 different available gray levels, while an 8-bit display device can display a pixel in one of 256 available gray levels. For instance, continuous tone ("contone") output devices typically display 256 gray levels; sometimes, a 16 gray-level device is called a contone device. Other output display devices may only be able to display a pixel in one of 2 available gray levels, e.g., black or white. These "bi-level" or "halftone" display devices include some laser printers, ink jet printers, other black and white printers, monochrome monitors, image setters, color output devices having bi-level output for each color component, etc.
Output display devices also typically are able to display additional gray levels by adjusting the spatial density of pixels in "pixel clusters" (also called "halftone cells"). This process of displaying additional gray levels is known as "dithering" or "halftoning." Dithering typically maps the pixels in the original image to available gray levels on the device. A pixel cluster is a group of one or more pixels that is repeated across an area to provide a simulated gray level, where at least two pixels in the pixel cluster are at different gray levels. For example, in a bi-level scheme having two gray levels, some of the pixels of the pixel cluster are displayed as black (dark), while other pixels in the cluster are white (light). By adjusting the number of pixels in the cluster that are black and white, different gray levels can be simulated (typically, contone devices do not use dithering). If the spatial resolution of the clusters is high enough, then a viewer will see the cluster as a shade of gray. For example, a circular dot pattern in each pixel cluster is commonly used in print devices, where the dot is made larger or smaller for each gray level to be represented. Or, a checkerboard pattern of black and white pixels can be used, where black and white pixels are alternated in the pixel cluster such that no pixel is adjacent to a pixel having the same gray level within the cluster. These patterns are often used to provide an intermediate gray level between extreme black and white gray levels. The number of black pixels in the cluster can be increased to create a darker gray level, and the number of white pixels can be increased to create a lighter gray level.
An image often may be of poor visual quality. For example, an image may have a low spatial resolution, where the pixels of the image are relatively large and can be noticed by a human viewer of the image as "jagged" edges on lines and objects rather than as smooth edges. An image also may have a low gray level resolution, i.e., the image may only include a small number of gray levels and/or the output device may only be able to display a small number of gray levels. The viewer can thus notice undesired large transitions or contours between different pixel gray levels where a smooth transition of gray levels (i.e., a "blend") may be desired.
An image may often be processed to increase the visual quality of the image. Image interpolation is one method by which the visual quality of an image can be increased. FIG. 1 is a block diagram of a standard image interpolation process 10. An original image 12 is input to an interpolation processor 14 implemented on a computer system. The interpolation processor 14 determines the resolution of the original image and the resolution of a primary target display device 16 which is to be used to display the image. An expansion factor 18 (or scale factor) is determined which is the multiplier by which the spatial resolution of the original image will be increased (if necessary) when displaying the image. The interpolation processor 14 applies the expansion factor in an interpolation process which produces an interpolated image 20. The interpolated image is then provided to the target display device 16 to be displayed, or the interpolated image can be stored, processed, sent to a different display device, or otherwise manipulated. The interpolated image 20 is usually of higher spatial resolution and may, in some cases, also be of higher gray level resolution than the original image, and thus is generally of higher visual quality than the original image, i.e., the interpolated image looks "smoother" in both shape and color and is more realistic.
The process of interpolation is illustrated in greater detail with respect to FIGS. 2a and 2b. FIG. 2a shows a pictorial representation of two adjacent pixels 22 and 24 which are included in original image 12 and which are shown as they would be displayed on a display device along an x-axis 23 and a y-axis 21. Pixels 22 and 24 have only two gray levels: black (or dark) and white (or light), where pixel 22 is a black pixel, and pixel 24 is a white pixel. The centers 26 of the pixels are also shown, since interpolation is often performed with reference to the pixel centers.
FIG. 2b is a graph 28 showing the brightness level (i.e., gray level) of pixels 22 and 24 of FIG. 2a. The vertical axis B represents the brightness level of the pixels, where a level of 1 indicates black and a level of 0 indicates white (these values can designate other gray levels in different embodiments). The x-axis 23 is provided to delineate the x spatial dimension of the pixels over which the original image is to be interpolated. Graph function 30 is provided at a brightness of one since it corresponds to black pixel 22, and graph function 32 is at a brightness of zero since it corresponds to the white pixel 24.
FIGS. 3a and 3b represent an interpolated image derived from the original image pixels 22 and 24 of FIGS. 2a and 2b. FIG. 3a shows a graph 34 similar to graph 28, in which the brightness for the interpolated pixels is represented on the vertical axis and the x-axis is the horizontal axis. FIG. 3b shows the x-y planar view of the interpolated pixels as displayed. An expansion factor of 3 has been applied to the pixels 22 and 24 to create an interpolated image having three times the resolution of the original image. The pixels have been interpolated in the x-dimension only. The area 36 between the centers 26 of the interpolated pixels is preferably processed with respect to pixel pair 22 and 24. This area 36 now has a total of four gray levels, represented as the levels of 0, 1/3, 2/3, and 1. An expansion factor of X creates X-1 intermediate gray levels. These gray level values are evenly distributed between the brightness values of the two original pixels (0 and 1). Thus, an interpolated pixel 38 having 1/3 the width of the original pixel 22 is centered around pixel center 26 a, having a graph function 40 at the brightness level of 1. A similar interpolated pixel 42 is centered around pixel center 26b and has a graph function 44 at a brightness level of 0. Interpolated pixel 46 has a brightness value of 2/3 as shown by graph function 48 and is positioned from pixel 38 to the midline 47 between the original pixels. Interpolated pixel 50 has a brightness value of 1/3 as shown by graph line 52 and is positioned between pixel 46 and pixel 42.
The brightness level of pixels 54 outside the area between the centers of the pixels 22 and 24 are determined by the interpolated values between the centers of one of the original pixels 22 and 24 and an adjacent pixel (not shown). For example, if an original pixel (not shown) positioned adjacent and to the left of original pixel 22 has a brightness level of zero (white), then pixel 54a might have a brightness level of 2/3, as shown by dotted graph function 56. A brightness value can be similarly determined for pixel 54b. If there are no pixels adjacent to an original pixel in a particular direction, then the pixels 54a and 54b can be provided with a default gray level (brightness level), such as the brightness of the appropriate original pixel 22 or 24.
FIGS. 4a and 4b are diagrammatic illustrations of an example of two-dimensional (or "bilinear") interpolation. Original pixels 58, 60, 62, and 64 have been interpolated by an expansion factor of 3 in both x- and y-dimensions between the centers 26 of the pixels, resulting in an image resolution three times greater than the original resolution in both dimensions. Interpolated pixels 66 centered on pixel centers 26 have a brightness level equal to the brightness level of the original pixels. Intermediate Pixels 68 have intermediate brightness values as determined by the brightness values of the pixels surrounding the intermediate pixels. For example, the gray levels of edge intermediate pixels 70 are preferably determined first as described with reference to FIGS. 3a and 3b. The gray levels of interior in termediate pixels 72 are then preferably determined in either an x- or y-direction. For example, intermediate pixels 72a and 72b have intermediate gray levels between the brightness values of edge pixels 70a and 70b, determined in an x-direction. The gray levels of pixels 74 outside the area between the centers of the pixels are determined from the appropriate adjacent pixels (not shown).
A problem with image interpolation is that interpolated images can become exceedingly large in terms of required storage space so as to become inefficient to store and manipulate. The magnitude of the expansion factor determines how large the interpolated image is, where too high of an expansion factor causes the interpolated image to exceed available or desired memory space. For example, assume an original image includes 2 gray levels of 0 and 1. An expansion factor of X will create X-1 interpolated pixels for each original pixel, and create X-1 gray levels, for a total of X+1 gray levels in the interpolated image. For example, an expansion factor of 255 creates 254 interpolated pixels per original pixel and a total of 256 gray levels. The interpolated image has a new spatial resolution that is increased over the original resolution by a factor of X.sup.2, e.g., 255.times.255=65,025 (in number of pixels). The greater spatial resolution (and gray levels resolution, if it has increased) consume a much larger amount of memory space, and may exceed the available or desired amount of memory space.
In addition, too high of an expansion factor may provide more gray levels than can be displayed by a particular output display device. For example, using dithering, a 300 dpi bi-level output display device may be able to display 25 gray levels. If an interpolation process expands the number of gray levels in an image to be greater than 25, then some of the gray levels will not be displayed on the output device. This can cause an uneven distribution of gray levels in the image that affects the quality of the image.
These problems have been addressed in the prior art by limiting the expansion factor for interpolated images by various methods. One method is to limit the spatial resolution of the interpolated image 20 to the maximum possible spatial resolution of the target display device. For example, if the target display device displays a maximum resolution D of 600 dots per inch, and the original image resolution I is 10 pixels per inch, then the expansion factor is provided with a maximum limit of D/I=600/10=60. This first method can be employed separately for each dimension of the interpolated image. Another method used in the prior art is to limit the gray level resolution of the interpolated image to the maximum possible gray level resolution of the target display device. For example, PostScript devices are typically limited to a maximum of 8-bit output or 256 gray levels (e.g., using dithering), and the expansion factor can be limited such that the interpolated image includes no more than 256 gray levels. A third method limits the expansion factor by calculating twice the screen ruling of the target display device divided by the original image resolution. The "screen ruling" or "halftone frequency" is a measure of resolution for half-tone output display devices, also known as a half-tone frequency. This third rule is a "rule of thumb" used in the printing industry when scanning images for later printing on a press. Previous methods may also use a combination of all these methods to limit the expansion factor.
Problems are inherent when using the prior art methods of limiting an expansion factor and the resolution of the interpolated image. The first two methods of the prior art, limiting the spatial resolution of the interpolated image and limiting the gray level resolution to a known maximum, may still produce unnecessarily high expansion factors, making the resulting image consume more memory space than is necessary. These larger-than-necessary images can also cause inefficiencies such as longer print and transfer times in subsequent subsystems which process or display the image. The third (approximate) method of the prior art, limiting by screen ruling or another similar rule of thumb, may similarly provide an inefficient interpolated image size and also is not effective for display devices that do not use traditional screens with screen rulings, such as printers with stochastic screening. The third method of using a rule of thumb factor may also provide too low an expansion factor so that the interpolated image does not utilize all the available spatial or gray level resolution of the target display device, resulting in a displayed image having poor visual quality.